package interview.huawei.tjt.training.huisu;

import java.util.*;

/**
 * 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
 *
 * 示例:
 *
 * 输入: [1,2,3]
 * 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
 */
public class Permute {

    private static List<LinkedList<Integer>> result = new ArrayList();
    private static LinkedList<Integer> path = new LinkedList<>();
    private static boolean[] used;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String[] str = sc.nextLine().split(",");
            int[] nums = new int[str.length];
            for (int i = 0; i < str.length; i ++) {
                if (!str[i].equals("") && str[i] != null) {
                    nums[i] = Integer.parseInt(String.valueOf(str[i]));
                }
            }
            if (nums.length == 0) {
                System.out.println(result);
            } else {
                used = new boolean[nums.length];
                helper(nums);
                System.out.println(result);
            }
        }
    }

    private static void helper (int[] nums) {
        if (path.size() == nums.length) {
            result.add(new LinkedList<>(path));
        }

        for (int i = 0; i < nums.length; i ++) {
//            if (path.size() > nums.length) break;
            if (used[i]){
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            helper(nums);
            path.removeLast();
            used[i] = false;
        }
    }

}
